#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
using pii = pair<int, int>;
vector<int> nums3;
vector<int> nums4;
class Greater
{
public:
    bool operator()(pii p1, pii p2)
    {
        return (nums3[p1.first] + nums4[p1.second]) > (nums3[p2.first] + nums4[p2.second]);
    }
};
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k)
    {
        nums3 = nums1;
        nums4 = nums2;
        vector<vector<int>> ret(k);
        priority_queue<pii, vector<pii>, Greater> pq;
        for (int i = 0;i < nums1.size();++i)
        {
            pq.push({ i,0 });
        }
        for (int i = 0;i < k;++i)
        {
            int a = pq.top().first;
            int b = pq.top().second;
            pq.pop();
            ret[i] = { nums1[a],nums2[b] };
            if (b + 1 < nums2.size())
            {
                pq.push({ a,b + 1 });
            }
        }
        return ret;
    }
};